package oj.oj_JZ31;
//JZ31 栈的压入、弹出序列
import java.util.*;

public class Solution2 {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if (pushA.length != popA.length) {
            return false;
        }

        int pushIndex = 0;
        int popIndex = 0;

        // 定义栈
        Deque<Integer> stack = new LinkedList<>();

        // 遍历每个出栈序列的元素
        while (popIndex < popA.length) {
            // 第一个要出栈的，就是 [0] 的元素
            // 使用头删的方式，把这个元素取出来
            int popE = popA[popIndex++];
            // 检查栈顶元素是不是这个 popE
            while (stack.isEmpty() || stack.peek() != popE) {
                // 从入栈序列中取出元素，放入栈中
                // 首先应该拿入栈元素的 [0] 的元素，头删
                if (pushIndex >= pushA.length) {
                    // 说明 栈顶元素 和 要出栈的元素不相等 && 没有元素可供入栈了
                    return false;
                }
                int pushE = pushA[pushIndex++];
                stack.push(pushE);
            }

            // 说明下一个要出栈的元素和栈顶元素相等了
            stack.pop();    // 弹出栈顶元素，循环取检查下个要出栈的元素
        }

        return true;
    }
}
